package binarysearch;

/**
 * 二分 + bfs 检查
 */
public class 水位上升的泳池中游泳_778 {
            int[][] moves = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
            // 找一条最大值最小的路径的最大值
            public int swimInWater(int[][] grid) {
                // 因为t时刻整个池子中的水位线为 t
                // 求耗时多久就是求一个水位线 ，该水位线大于等于所有的dfs路径上的水位线使得能够从 (0,0) -> (n-1, n-1)
                // 求大于等于  用 l - mid + 1  mid - r
                int n = grid.length;
                // 至少到两个平台最大高度才能行    如果n = 2 那么  r  = 3
                int l = Math.max(grid[0][0], grid[n - 1][n - 1]), r = n * n - 1;
                while(l < r) {
                    int mid = l + (r - l) / 2;  // 注意  l + (r - l) >> 1 中  + 比 >> 优先级高  结果有问题
                    boolean connected = dfsConnected(mid, 0, 0, grid,  new boolean[n][n]);
                    //System.out.println(l + " - " + mid + " - " + r + " : connected " + connected);
                    if(connected) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                return l;
            }
            // 水位线 t时刻 为t
            private boolean dfsConnected(int t, int x, int y, int[][] grid, boolean[][] visited) {
                int n = grid.length;
                if(x == n - 1  && y == n - 1) {
                    return true; // 到达目标  t水位线是可以的
                }
                visited[x][y] = true;
                for(int[] move: moves) {
                    //下一行代码如果用 x += move[0];  y += move[1]; 是有问题的   dfs方格遍历中不能使用x自身来上下左右移动  比如先 x + 1 y + 0  后面会对新的点进行上左右移动 而不是原来的点
                    // 方格dfs需要使用新的点
                    int nx = x + move[0];  int ny = y +  move[1];
                    if(nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] <= t) {
                        if(dfsConnected(t,nx,ny, grid, visited)) return true;
                    }
                }
                return false;
            }
        }